package org.example;

public class Test2 {
    //leetcode 474 一和零 https://leetcode.cn/problems/ones-and-zeroes/description/
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j][k]表示从前i个物品中选择装入背包，0和1的数量分别为j和k的自己的最大长度
        int len = strs.length;
        int[][][] dp = new int[len+1][m+1][n+1];
        int zeroCount = 0, oneCount = 0;
        for (int i = 1; i <= len; i++) {
            zeroCount = zeroCount(strs[i-1]);
            oneCount = strs[i-1].length() - zeroCount;
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if (j >= zeroCount && k >= oneCount) {
                        dp[i][j][k] = Math.max(dp[i][j][k],dp[i-1][j-zeroCount][k-oneCount] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    private int zeroCount(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') count++;
        }
        return count;
    }

    //优化
    public int findMaxForm1(String[] strs, int m, int n) {
        //dp[i][j][k]表示从前i个物品中选择装入背包，0和1的数量分别为j和k的自己的最大长度
        int len = strs.length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= len; i++) {
            int zeroCount = 0, oneCount = 0;
            for (char c : strs[i-1].toCharArray()) {
                if (c == '0') zeroCount++;
                else oneCount++;
            }
            for (int j = m; j >= zeroCount; j--) {
                for (int k = n; k >= oneCount; k--) {
                    dp[j][k] = Math.max(dp[j][k],dp[j-zeroCount][k-oneCount] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        String[] arr = {"11111","100","1101","1101","11000"};
        test2.findMaxForm(arr,5,7);
        System.out.println(666);
    }
}
